Link List
Q21.
Suppose there are \left \lceil log n \right \rceil sorted lists of \left \lfloor n/log n \right \rfloor elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)Q22.
Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best-known algorithm to delete the node x from the list ?Q23.
Suppose each set is represented as a linked list with elements in arbitray order. Which of the operations among union, intersection, membership, cardinality will be the slowest?Q24.
Consider the function f defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p->next == NULL) || ((P->data <= p->next->data) && f(p->next))); } For a given linked list p, the function f returns 1 if and only ifQ25.
A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?Q26.
In the worst case, the number of comparisons needed to search a single linked list of length n for a given element isQ27.
The concatenation of two lists is to be performed on O(1) time. Which of the following implementations of a list should be used?Q28.
For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons ofQ29.
Which of the following statements is true? I. As the number of entries in a hash table increases, the number of collisions increases. II. Recursive programs are efficient III. The worst case complexity for Quicksort is O(n^2) IV. Binary search using a linear linked list is efficientQ30.
Linked lists are not suitable data structures for which one of the following problems?